This invention relates in general to recording transactions in a transaction log, and more particularly to recording transactions in a transaction log using a chronological list superimposed on an indexed list.
The telecommunications industry is on the verge of a major change in the way local telephone service is provided. Traditionally, a single service provider provided local service for all telephone subscribers within a local market. However, under the 1996 Telecommunications Act, multiple service providers may operate within a local market and compete for local subscribers. In the competition for local subscribers, the existing service provider has an advantage over other service providers if local telephone subscribers must change telephone numbers to change service providers. To eliminate any advantage that the existing local service provider may have due to a subscriber""s reluctance to change telephone numbers, a local telephone subscriber is permitted to keep an existing telephone number even though the subscriber changes service providers. Local Number Portability (xe2x80x9cLNPxe2x80x9d) is the mechanism which allows a local telephone subscriber to keep an existing telephone number even though the subscriber changes local service providers.
Currently, each subscriber telephone line is assigned a directory number or telephone number. A directory number is the number that is dialed or input by a calling party to place a telephone call. Each directory number in the United States includes ten digits (e.g. 404-222-2500). A directory number contains a three digit area code (xe2x80x9cNPAxe2x80x9d) followed by a three digit exchange code (xe2x80x9cNXXxe2x80x9d). The first six digits of a directory number are referred to as the xe2x80x9cNPA-NXX.xe2x80x9d For example, there are 10,000 directory numbers that start with the NPA-NXX 404-222 (i.e., 404-222-0001, 404-222-0002, etc.).
In a non-LNP enabled telecommunications network, each NPA-NXX is typically assigned to a single switch. However, in an LNP enabled telecommunications network, an NPA-NXX is no longer assigned to a single switch. A directory number may be xe2x80x9cportedxe2x80x9d to a switch served by a different service provider so the NPA-NXX of a directory number no longer uniquely identifies a switch. Traditional telephone routing procedures assume that the NPA-NXX of a directory number uniquely identifies a switch. To accommodate LNP, new telephone routing procedures are needed because the NPA-NXX of a directory number no longer uniquely identifies a switch.
To route a telephone call in an LNP enabled telecommunications network, the originating switch may refer to an LNP database to determine which switch serves a particular directory number. The LNP database includes a list of directory numbers and corresponding Local Routing Numbers (xe2x80x9cLRNxe2x80x9d). An LRN identifies the switch which serves the directory number. Each local service provider may maintain its own LNP database. For example, if a telephone call is placed from a directory number in Network A to a directory number in Network B, the originating switch in Network A refers to an LNP database in Network A to determine where the call should be routed. The LNP database includes an entry for the called directory number which indicates that the directory number is served by a switch in Network B. Therefore, the originating switch in Network A routes the telephone call to a switch in Network B.
When a subscriber changes local service providers, the subscriber""s directory number is ported to a network managed by a different local service provider. To reflect the change, the local service providers must update their respective LNP databases with network information for the new local service provider. Ideally, all of the LNP databases are updated simultaneously so that calls to the subscriber""s directory number are properly routed after the change in service providers. However, in reality, there is a delay between updates because the updates are performed independently by each local service provider. If the LNP databases are not updated simultaneously, then a non-call associated message may xe2x80x9cloopxe2x80x9d between local service provider networks, i.e., the message may be routed between the networks in a loop until both LNP databases are updated.
For example, looping may occur if a subscriber moves from local service provider A to local service provider B and the LNP databases are not all updated when a CLASS (Custom Local Area Signaling Services) service such as the xe2x80x9cRepeat Dialingxe2x80x9d service is invoked for the subscriber""s directory number. Prior to the move, the LNP database for local service provider A and the LNP database for local service provider B both indicate that the subscriber""s directory number is served by a switch in Network A. After the move, local service provider A updates its LNP database to indicate that the subscriber""s directory number is served by a switch in Network B. However, local service provider B does not immediately update its LNP database so its LNP database still indicates that the customer""s number is served by a switch in Network A.
If the subscriber""s directory number is initially busy, Repeat Dialing may be invoked to monitor the directory number to determine when the directory number is available. Once the subscriber""s directory number is available, the call may be completed. Non-call associated messages are used to monitor the status of the subscriber""s directory number. Some of the messages require Global Title Translation (xe2x80x9cGTTxe2x80x9d). If the call to the subscriber""s directory number originates in Network A, the Network A switch queries the LNP database of Network A to determine which switch serves the directory number. The LNP database of Network A indicates that a switch in Network B serves the directory number, so Network A sends a message to Network B to determine the status of the called number. When Network B receives the message, the LNP database of Network B is queried to determine which switch serves the directory number. The LNP database of Network B indicates that the message should be routed to a switch in Network A so Network B sends the message back to Network A. The message continues to loop between Network A and Network B until the LNP database of Network B is updated. Looping may also occur if there is an error in one of the LNP databases. An error may arise from a human error or a processing error.
Looping is a problem because a looping message consumes network resources and negatively impacts network performance and reliability. Looping messages also create an overload condition on the network, causing legitimate calls to fail. Several solutions have been proposed to solve the looping problem. One proposed solution involves marking a message with a xe2x80x9cdirtyxe2x80x9d bit. A dirty bit is set by the originating network before the message is sent. The originating network checks the dirty bit for each message it receives from another network. If the dirty bit is set, then the originating network detects a loop. A disadvantage of the dirty bit proposal is that the dirty bit must be preserved by all local service providers. However, there is no provision for a dirty bit in the existing message routing protocol, so there is no guarantee that the dirty bit will be preserved.
Another proposed solution is xe2x80x9cgateway screeningxe2x80x9d. This solution requires that a network screen messages received from other networks to detect a looping message. A message received from another network is screened to determine whether the message originated in the network receiving the message. If the message originated in the network receiving the message, then the message is dropped. A disadvantage of this solution is that it will only detect loops involving an originating network. If a loop occurs between two non-originating networks, it is not detected.
A third proposed solution is transaction ID logging. Transaction ID logging maintains a log of messages recently sent to other networks and compares a message received from another network to the message log. If the received message matches a message in the log, a loop is detected. The log is maintained so that it only contains messages sent within a predetermined period of time. An advantage of transaction ID logging is that it is a self-sufficient solution. Transaction ID logging may be implemented by one local service provider regardless of whether other local service providers implement it. Another advantage is that it works with existing message protocols.
Although transaction ID logging is theoretically appealing, it has not been previously implemented because of concerns that it would adversely impact network performance. The Illinois Commerce Commission (xe2x80x9cICCxe2x80x9d), a group formed to study message looping in LNP enabled telecommunications networks and to provide recommended solutions, considered but did not pursue transaction ID logging. The IIC Subcommittee concluded that transaction ID logging was too processor intensive, and therefore, did not pursue transaction ID logging.
Accordingly, there is a need in the art for an implementation of transaction ID logging in which the time to compare a new transaction to the existing transaction entries in the transaction log is minimized. There is also a need in the art for an implementation of transaction ID logging in which the time to maintain a transaction log is minimized.
The present invention satisfies the above-described needs by using a chronological list superimposed on an indexed list to implement transaction ID logging. The chronological list expedites maintaining the log and the indexed list expedites searching the log. In an LNP enabled telecommunications network, the present invention may be used to detect messages looping between networks. Generally described, the present invention provides a system and method for recording transactions, such as non-call associated messages, in a transaction log using a chronological list superimposed on an indexed list. A transaction log includes a number of transaction entries. Each transaction entry corresponds to a previous transaction. When a new transaction is received, the new transaction is compared to the existing transactions in the transaction log. If a match is detected between the new transaction and an existing transaction, a loop is detected. Once a transaction loop is detected, appropriate action may be taken to break the loop. To ensure that a valid subsequent transaction is not detected as a looping transaction, stale transaction entries are deleted from the transaction log. Typically, a transaction entry is stale if it has been in the transaction log longer than a predetermined maintenance period.
A transaction entry typically includes a transaction descriptor field, a time stamp field, a chronological list pointer field and an indexed list pointer field. The transaction descriptor field contains a transaction descriptor which identifies the transaction and other transaction information. The time stamp field contains a time stamp indicating when the transaction was initiated. The chronological list pointer field may contain a chronological list pointer pointing to the next oldest transaction entry. The indexed list pointer field may contain an indexed list pointer pointing to another transaction entry with the same index.
Each transaction entry in the transaction log is placed in both the chronological list and the indexed list. The chronological list orders the transaction entries from the oldest transaction entry to the latest transaction entry. Chronological list pointers are associated with the transaction entries in the chronological list. For example, a first chronological list pointer points to the oldest transaction entry and a last chronological list pointer points to the latest transaction entry. The order of the remaining transaction entries in the chronological list is maintained using chronological list pointers. A chronological list pointer links a transaction entry to the next oldest transaction entry. The chronological list minimizes the time needed to identify and delete a stale transaction entry.
The indexed list is a list of indexed list entry pointers. Each indexed list entry pointer corresponds to an index and points to a transaction entry with the same index. The index for a transaction entry may be determined by hashing the transaction descriptor for the transaction entry. If there is more than one transaction entry with the same index, then the transaction entries are linked together via the indexed list pointer fields of the transaction entries. For example, if there are two transaction entries with the same index, then the indexed list entry pointer points to the first transaction entry and the indexed list pointer field of the first transaction entry points to the next transaction entry. The indexed list reduces the number of transaction entries which must be searched to determine whether there is a match between a new transaction and an existing transaction. Reducing the number of transaction entries minimizes the time needed to compare a new transaction with an existing transaction.
To maintain the transaction log, the transaction entries are checked to determine whether any of the transaction entries have been stored in the transaction log for longer than the predetermined maintenance period. The first chronological list pointer is used to identify the oldest transaction entry in the transaction log. The time stamp field of the oldest transaction entry is checked to determine whether the transaction entry is stale. If the oldest transaction entry is stale, then the transaction entry is deleted from the chronological list and the indexed list. To delete the oldest transaction entry from the chronological list, the first chronological pointer is updated to point to the next oldest transaction entry. To delete the oldest transaction entry from the indexed list, the indexed list entry pointer corresponding to the oldest transaction entry is updated. If the indexed list entry pointer field of the oldest transaction entry contains an end of list indicator, then there are no other transaction entries with the same index and the indexed list entry pointer is updated to contain an end of list indicator. If the indexed list entry pointer field of the oldest transaction entry contains a pointer to another transaction entry, then the indexed list entry pointer is updated to point to that transaction entry.
To compare a new transaction with the existing transactions in the transaction log, the index for the new transaction is calculated. The index identifies an indexed list entry pointer corresponding to the index. If there is no transaction entry which corresponds to the index, then the indexed list entry pointer contains an end of list indicator. Otherwise, the indexed list entry pointer contains a pointer to a transaction entry corresponding to the index. If there is more than one transaction entry corresponding to the index, then the indexed list pointer field of the transaction entry corresponding to the index contains a pointer to another transaction entry. Once the transaction entries corresponding to the index are identified, the transaction information for each transaction entry is compared to the transaction information for the new transaction. If there is a match, then a loop is detected. If there is no match, a new transaction entry is created for the new transaction and the new transaction entry is added to the transaction log.
To add a new transaction entry to the transaction log, the last chronological list pointer is updated to point to the new transaction entry. The chronological list pointer field of the transaction entry previously pointed to by the last chronological list pointer is updated to point to the new transaction entry. If the indexed list entry pointer corresponding to the index for the new transaction contains an end of list indicator, the indexed list entry pointer is updated to point to the new transaction entry. Otherwise, the indexed list pointer field of the last transaction entry corresponding to the index is updated to point to the new transaction identifier.
Using a chronological list superimposed on an indexed list, solves the problems of quickly maintaining and searching the transaction log. The chronological list minimizes the time required to identify and delete the oldest transaction entries. There is no need to search the entire transaction log to locate the oldest transaction entry because the first chronological list pointer points to the oldest transaction entry. Similarly, only those transaction entries with the same index as the new transaction are searched to determine if a new transaction matches an existing transaction in the transaction log. The search time is minimized because only those transaction entries with the same index are searched.
These and other aspects, features and advantages of the present invention may be more clearly understood and appreciated from a review of the following detailed description of the disclosed embodiments and by reference to the appended drawings and claims.